// https://www.lintcode.com/problem/largest-triangle-area/

public class Solution {
    /**
     * @param points: List[List[int]]
     * @return: return a double
     */
    public double largestTriangleArea(int[][] points) {
        // write your code here
        double ret = 0;
        for (int i = 0; i < points.length - 2; ++i) {
            for (int j = i + 1; j < points.length - 1; ++j) {
                for (int k = j + 1; k < points.length; ++k) {
                    double area = points[i][0] * points[j][1] + 
                                  points[j][0] * points[k][1] +
                                  points[k][0] * points[i][1] -
                                  points[i][1] * points[j][0] -
                                  points[j][1] * points[k][0] -
                                  points[k][1] * points[i][0];
                    area = 0.5 * Math.abs(area);
                    if (area > ret) {
                        ret = area;
                    }
                }
            }
        }
        return ret;
    }
}